/****************************************************************************
* TMesh                                                                  *
*                                                                           *
* Consiglio Nazionale delle Ricerche                                        *
* Istituto di Matematica Applicata e Tecnologie Informatiche                *
* Sezione di Genova                                                         *
* IMATI-GE / CNR                                                            *
*                                                                           *
* Authors: Marco Attene                                                     *
* Copyright(C) 2013: IMATI-GE / CNR                                         *
* All rights reserved.                                                      *
*                                                                           *
* This program is dual-licensed as follows:                                 *
*                                                                           *
* (1) You may use TMesh as free software; you can redistribute it and/or *
* modify it under the terms of the GNU General Public License as published  *
* by the Free Software Foundation; either version 3 of the License, or      *
* (at your option) any later version.                                       *
* In this case the program is distributed in the hope that it will be       *
* useful, but WITHOUT ANY WARRANTY; without even the implied warranty of    *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             *
* GNU General Public License (http://www.gnu.org/licenses/gpl.txt)          *
* for more details.                                                         *
*                                                                           *
* (2) You may use TMesh as part of a commercial software. In this case a *
* proper agreement must be reached with the Authors and with IMATI-GE/CNR   *
* based on a proper licensing contract.                                     *
*                                                                           *
****************************************************************************/

#include "TMesh/marchIntersections.h"

namespace T_MESH
{

int mc_ints::compare(const void *e1, const void *e2)
{
 mc_ints *a = (mc_ints *)e1;
 mc_ints *b = (mc_ints *)e2;
 coord& l1 = a->ic;
 coord& l2 = b->ic;
 if (l1 < l2) return -1;
 if (l2 < l1) return 1;

 return 0;
}

UBYTE mc_cell::lookup() const
{
	UBYTE l = 0;
	int v[8] = { 0, 0, 0, 0, 0, 0, 0, 0 }, m;

	if (ints[0]) if (ints[0]->sg) v[1] = 1; else v[0] = 1;
	if (ints[1]) if (ints[1]->sg) v[2] = 1; else v[1] = 1;
	if (ints[2]) if (ints[2]->sg) v[2] = 1; else v[3] = 1;
	if (ints[3]) if (ints[3]->sg) v[3] = 1; else v[0] = 1;

	if (ints[4]) if (ints[4]->sg) v[5] = 1; else v[4] = 1;
	if (ints[5]) if (ints[5]->sg) v[6] = 1; else v[5] = 1;
	if (ints[6]) if (ints[6]->sg) v[6] = 1; else v[7] = 1;
	if (ints[7]) if (ints[7]->sg) v[7] = 1; else v[4] = 1;

	if (ints[8]) if (ints[8]->sg) v[4] = 1; else v[0] = 1;
	if (ints[9]) if (ints[9]->sg) v[5] = 1; else v[1] = 1;
	if (ints[10]) if (ints[10]->sg) v[6] = 1; else v[2] = 1;
	if (ints[11]) if (ints[11]->sg) v[7] = 1; else v[3] = 1;

	if (v[0] && !ints[0]) v[1] = 1;
	if (v[0] && !ints[3]) v[3] = 1;
	if (v[0] && !ints[8]) v[4] = 1;

	if (v[1] && !ints[0]) v[0] = 1;
	if (v[1] && !ints[1]) v[2] = 1;
	if (v[1] && !ints[9]) v[5] = 1;

	if (v[2] && !ints[1]) v[1] = 1;
	if (v[2] && !ints[2]) v[3] = 1;
	if (v[2] && !ints[10]) v[6] = 1;

	if (v[3] && !ints[2]) v[2] = 1;
	if (v[3] && !ints[3]) v[0] = 1;
	if (v[3] && !ints[11]) v[7] = 1;

	if (v[4] && !ints[4]) v[5] = 1;
	if (v[4] && !ints[7]) v[7] = 1;
	if (v[4] && !ints[8]) v[0] = 1;

	if (v[5] && !ints[4]) v[4] = 1;
	if (v[5] && !ints[5]) v[6] = 1;
	if (v[5] && !ints[9]) v[1] = 1;

	if (v[6] && !ints[5]) v[5] = 1;
	if (v[6] && !ints[6]) v[7] = 1;
	if (v[6] && !ints[10]) v[2] = 1;

	if (v[7] && !ints[6]) v[6] = 1;
	if (v[7] && !ints[7]) v[4] = 1;
	if (v[7] && !ints[11]) v[3] = 1;

	for (m = 0; m<8; m++) l |= (((UBYTE)((v[m]) ? (1) : (0))) << m);

	return l;
}


UBYTE mc_cell::lookdown()
{
	int v[8] = { 0, 0, 0, 0, 0, 0, 0, 0 }, m;
	UBYTE i;
	const UBYTE c1[12] = { 0, 1, 3, 0, 4, 5, 7, 4, 0, 1, 2, 3 };
	const UBYTE c2[12] = { 1, 2, 2, 3, 5, 6, 6, 7, 4, 5, 6, 7 };
	const UBYTE e1[8] = { 0, 0, 2, 2, 4, 4, 6, 6 };
	const UBYTE e2[8] = { 3, 1, 1, 3, 7, 5, 5, 7 };
	const UBYTE e3[8] = { 8, 9, 10, 11, 8, 9, 10, 11 };

	for (i = 0; i < 12; i++) if (ints[i])
	{
		if (ints[i]->sg) v[c2[i]] = 1; else v[c1[i]] = 1;
	}

	for (m = 0; m < 8; m++) if (v[m])
	{
		if (!ints[e1[m]] && !v[c1[e1[m]]]) { v[c1[e1[m]]] = 1; if (c1[e1[m]] < m) { m = -1; continue; } }
		if (!ints[e1[m]] && !v[c2[e1[m]]]) { v[c2[e1[m]]] = 1; if (c2[e1[m]] < m) { m = -1; continue; } }
		if (!ints[e2[m]] && !v[c1[e2[m]]]) { v[c1[e2[m]]] = 1; if (c1[e2[m]] < m) { m = -1; continue; } }
		if (!ints[e2[m]] && !v[c2[e2[m]]]) { v[c2[e2[m]]] = 1; if (c2[e2[m]] < m) { m = -1; continue; } }
		if (!ints[e3[m]] && !v[c1[e3[m]]]) { v[c1[e3[m]]] = 1; if (c1[e3[m]] < m) { m = -1; continue; } }
		if (!ints[e3[m]] && !v[c2[e3[m]]]) { v[c2[e3[m]]] = 1; if (c2[e3[m]] < m) { m = -1; continue; } }
	}

	i = 0;
	for (m = 0; m<8; m++) i |= (((UBYTE)((v[m]) ? (1) : (0))) << m);

	return i;
}

int mc_cell::compare(const void *e1, const void *e2)
{
 mc_cell *a = (mc_cell *)e1;
 mc_cell *b = (mc_cell *)e2;
 int c;

 if ((c=(a->x - b->x)) < 0) return -1;
 if (c > 0) return 1;
 if ((c=(a->y - b->y)) < 0) return -1;
 if (c > 0) return 1;
 if ((c=(a->z - b->z)) < 0) return -1;
 if (c > 0) return 1;

 return 0;
}



void mc_cell::polygonize(Basic_TMesh *tin)
{
 ExtVertex *v[12];
 Edge *e1,*e2,*e3;
 int i,t[3];
 unsigned char lu = lookdown();

 static const char mc_triTable[256][20] =
 { 
  {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  8,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  1,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  8,  3, -1,  9,  8,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  8,  3, -1,  1,  2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 9,  2, 10, -1,  0,  2,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 2,  8,  3, -1,  2, 10,  8, -1, 10,  9,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 3, 11,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0, 11,  2, -1,  8, 11,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  9,  0, -1,  2,  3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1, 11,  2, -1,  1,  9, 11, -1,  9,  8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 3, 10,  1, -1, 11, 10,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0, 10,  1, -1,  0,  8, 10, -1,  8, 11, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 3,  9,  0, -1,  3, 11,  9, -1, 11, 10,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 9,  8, 10, -1, 10,  8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 4,  7,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 4,  3,  0, -1,  7,  3,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  1,  9, -1,  8,  4,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 4,  1,  9, -1,  4,  7,  1, -1,  7,  3,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  2, 10, -1,  8,  4,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 3,  4,  7, -1,  3,  0,  4, -1,  1,  2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 9,  2, 10, -1,  9,  0,  2, -1,  8,  4,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 2, 10,  9, -1,  2,  9,  7, -1,  2,  7,  3, -1,  7,  9,  4, -1, -1, -1, -1, -1},
  { 8,  4,  7, -1,  3, 11,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {11,  4,  7, -1, 11,  2,  4, -1,  2,  0,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 9,  0,  1, -1,  8,  4,  7, -1,  2,  3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 4,  7, 11, -1,  9,  4, 11, -1,  9, 11,  2, -1,  9,  2,  1, -1, -1, -1, -1, -1},
  { 3, 10,  1, -1,  3, 11, 10, -1,  7,  8,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1, 11, 10, -1,  1,  4, 11, -1,  1,  0,  4, -1,  7, 11,  4, -1, -1, -1, -1, -1},
  { 4,  7,  8, -1,  9,  0, 11, -1,  9, 11, 10, -1, 11,  0,  3, -1, -1, -1, -1, -1},
  { 4,  7, 11, -1,  4, 11,  9, -1,  9, 11, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 9,  5,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 9,  5,  4, -1,  0,  8,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  5,  4, -1,  1,  5,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 8,  5,  4, -1,  8,  3,  5, -1,  3,  1,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  2, 10, -1,  9,  5,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 3,  0,  8, -1,  1,  2, 10, -1,  4,  9,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 5,  2, 10, -1,  5,  4,  2, -1,  4,  0,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 2, 10,  5, -1,  3,  2,  5, -1,  3,  5,  4, -1,  3,  4,  8, -1, -1, -1, -1, -1},
  { 9,  5,  4, -1,  2,  3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0, 11,  2, -1,  0,  8, 11, -1,  4,  9,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  5,  4, -1,  0,  1,  5, -1,  2,  3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 2,  1,  5, -1,  2,  5,  8, -1,  2,  8, 11, -1,  4,  8,  5, -1, -1, -1, -1, -1},
  {10,  3, 11, -1, 10,  1,  3, -1,  9,  5,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 4,  9,  5, -1,  0,  8,  1, -1,  8, 10,  1, -1,  8, 11, 10, -1, -1, -1, -1, -1},
  { 5,  4,  0, -1,  5,  0, 11, -1,  5, 11, 10, -1, 11,  0,  3, -1, -1, -1, -1, -1},
  { 5,  4,  8, -1,  5,  8, 10, -1, 10,  8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 9,  7,  8, -1,  5,  7,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 9,  3,  0, -1,  9,  5,  3, -1,  5,  7,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  7,  8, -1,  0,  1,  7, -1,  1,  5,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  5,  3, -1,  3,  5,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 9,  7,  8, -1,  9,  5,  7, -1, 10,  1,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {10,  1,  2, -1,  9,  5,  0, -1,  5,  3,  0, -1,  5,  7,  3, -1, -1, -1, -1, -1},
  { 8,  0,  2, -1,  8,  2,  5, -1,  8,  5,  7, -1, 10,  5,  2, -1, -1, -1, -1, -1},
  { 2, 10,  5, -1,  2,  5,  3, -1,  3,  5,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 7,  9,  5, -1,  7,  8,  9, -1,  3, 11,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 9,  5,  7, -1,  9,  7,  2, -1,  9,  2,  0, -1,  2,  7, 11, -1, -1, -1, -1, -1},
  { 2,  3, 11, -1,  0,  1,  8, -1,  1,  7,  8, -1,  1,  5,  7, -1, -1, -1, -1, -1},
  {11,  2,  1, -1, 11,  1,  7, -1,  7,  1,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 9,  5,  8, -1,  8,  5,  7, -1, 10,  1,  3, -1, 10,  3, 11, -1, -1, -1, -1, -1},
  { 5,  7,  0, -1,  5,  0,  9, -1,  7, 11,  0, -1,  1,  0, 10, -1, 11, 10,  0, -1},
  {11, 10,  0, -1, 11,  0,  3, -1, 10,  5,  0, -1,  8,  0,  7, -1,  5,  7,  0, -1},
  {11, 10,  5, -1,  7, 11,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {10,  6,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  8,  3, -1,  5, 10,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 9,  0,  1, -1,  5, 10,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  8,  3, -1,  1,  9,  8, -1,  5, 10,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  6,  5, -1,  2,  6,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  6,  5, -1,  1,  2,  6, -1,  3,  0,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 9,  6,  5, -1,  9,  0,  6, -1,  0,  2,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 5,  9,  8, -1,  5,  8,  2, -1,  5,  2,  6, -1,  3,  2,  8, -1, -1, -1, -1, -1},
  { 2,  3, 11, -1, 10,  6,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {11,  0,  8, -1, 11,  2,  0, -1, 10,  6,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  1,  9, -1,  2,  3, 11, -1,  5, 10,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 5, 10,  6, -1,  1,  9,  2, -1,  9, 11,  2, -1,  9,  8, 11, -1, -1, -1, -1, -1},
  { 6,  3, 11, -1,  6,  5,  3, -1,  5,  1,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  8, 11, -1,  0, 11,  5, -1,  0,  5,  1, -1,  5, 11,  6, -1, -1, -1, -1, -1},
  { 3, 11,  6, -1,  0,  3,  6, -1,  0,  6,  5, -1,  0,  5,  9, -1, -1, -1, -1, -1},
  { 6,  5,  9, -1,  6,  9, 11, -1, 11,  9,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 5, 10,  6, -1,  4,  7,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 4,  3,  0, -1,  4,  7,  3, -1,  6,  5, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  9,  0, -1,  5, 10,  6, -1,  8,  4,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {10,  6,  5, -1,  1,  9,  7, -1,  1,  7,  3, -1,  7,  9,  4, -1, -1, -1, -1, -1},
  { 6,  1,  2, -1,  6,  5,  1, -1,  4,  7,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  2,  5, -1,  5,  2,  6, -1,  3,  0,  4, -1,  3,  4,  7, -1, -1, -1, -1, -1},
  { 8,  4,  7, -1,  9,  0,  5, -1,  0,  6,  5, -1,  0,  2,  6, -1, -1, -1, -1, -1},
  { 7,  3,  9, -1,  7,  9,  4, -1,  3,  2,  9, -1,  5,  9,  6, -1,  2,  6,  9, -1},
  { 3, 11,  2, -1,  7,  8,  4, -1, 10,  6,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 5, 10,  6, -1,  4,  7,  2, -1,  4,  2,  0, -1,  2,  7, 11, -1, -1, -1, -1, -1},
  { 0,  1,  9, -1,  4,  7,  8, -1,  2,  3, 11, -1,  5, 10,  6, -1, -1, -1, -1, -1},
  { 9,  2,  1, -1,  9, 11,  2, -1,  9,  4, 11, -1,  7, 11,  4, -1,  5, 10,  6, -1},
  { 8,  4,  7, -1,  3, 11,  5, -1,  3,  5,  1, -1,  5, 11,  6, -1, -1, -1, -1, -1},
  { 5,  1, 11, -1,  5, 11,  6, -1,  1,  0, 11, -1,  7, 11,  4, -1,  0,  4, 11, -1},
  { 0,  5,  9, -1,  0,  6,  5, -1,  0,  3,  6, -1, 11,  6,  3, -1,  8,  4,  7, -1},
  { 6,  5,  9, -1,  6,  9, 11, -1,  4,  7,  9, -1,  7, 11,  9, -1, -1, -1, -1, -1},
  {10,  4,  9, -1,  6,  4, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 4, 10,  6, -1,  4,  9, 10, -1,  0,  8,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {10,  0,  1, -1, 10,  6,  0, -1,  6,  4,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 8,  3,  1, -1,  8,  1,  6, -1,  8,  6,  4, -1,  6,  1, 10, -1, -1, -1, -1, -1},
  { 1,  4,  9, -1,  1,  2,  4, -1,  2,  6,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 3,  0,  8, -1,  1,  2,  9, -1,  2,  4,  9, -1,  2,  6,  4, -1, -1, -1, -1, -1},
  { 0,  2,  4, -1,  4,  2,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 8,  3,  2, -1,  8,  2,  4, -1,  4,  2,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {10,  4,  9, -1, 10,  6,  4, -1, 11,  2,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  8,  2, -1,  2,  8, 11, -1,  4,  9, 10, -1,  4, 10,  6, -1, -1, -1, -1, -1},
  { 3, 11,  2, -1,  0,  1,  6, -1,  0,  6,  4, -1,  6,  1, 10, -1, -1, -1, -1, -1},
  { 6,  4,  1, -1,  6,  1, 10, -1,  4,  8,  1, -1,  2,  1, 11, -1,  8, 11,  1, -1},
  { 9,  6,  4, -1,  9,  3,  6, -1,  9,  1,  3, -1, 11,  6,  3, -1, -1, -1, -1, -1},
  { 8, 11,  1, -1,  8,  1,  0, -1, 11,  6,  1, -1,  9,  1,  4, -1,  6,  4,  1, -1},
  { 3, 11,  6, -1,  3,  6,  0, -1,  0,  6,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 6,  4,  8, -1, 11,  6,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 7, 10,  6, -1,  7,  8, 10, -1,  8,  9, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  7,  3, -1,  0, 10,  7, -1,  0,  9, 10, -1,  6,  7, 10, -1, -1, -1, -1, -1},
  {10,  6,  7, -1,  1, 10,  7, -1,  1,  7,  8, -1,  1,  8,  0, -1, -1, -1, -1, -1},
  {10,  6,  7, -1, 10,  7,  1, -1,  1,  7,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  2,  6, -1,  1,  6,  8, -1,  1,  8,  9, -1,  8,  6,  7, -1, -1, -1, -1, -1},
  { 2,  6,  9, -1,  2,  9,  1, -1,  6,  7,  9, -1,  0,  9,  3, -1,  7,  3,  9, -1},
  { 7,  8,  0, -1,  7,  0,  6, -1,  6,  0,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 7,  3,  2, -1,  6,  7,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 2,  3, 11, -1, 10,  6,  8, -1, 10,  8,  9, -1,  8,  6,  7, -1, -1, -1, -1, -1},
  { 2,  0,  7, -1,  2,  7, 11, -1,  0,  9,  7, -1,  6,  7, 10, -1,  9, 10,  7, -1},
  { 1,  8,  0, -1,  1,  7,  8, -1,  1, 10,  7, -1,  6,  7, 10, -1,  2,  3, 11, -1},
  {11,  2,  1, -1, 11,  1,  7, -1, 10,  6,  1, -1,  6,  7,  1, -1, -1, -1, -1, -1},
  { 8,  9,  6, -1,  8,  6,  7, -1,  9,  1,  6, -1, 11,  6,  3, -1,  1,  3,  6, -1},
  { 0,  9,  1, -1, 11,  6,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 7,  8,  0, -1,  7,  0,  6, -1,  3, 11,  0, -1, 11,  6,  0, -1, -1, -1, -1, -1},
  { 7, 11,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 7,  6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 3,  0,  8, -1, 11,  7,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  1,  9, -1, 11,  7,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 8,  1,  9, -1,  8,  3,  1, -1, 11,  7,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {10,  1,  2, -1,  6, 11,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  2, 10, -1,  3,  0,  8, -1,  6, 11,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 2,  9,  0, -1,  2, 10,  9, -1,  6, 11,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 6, 11,  7, -1,  2, 10,  3, -1, 10,  8,  3, -1, 10,  9,  8, -1, -1, -1, -1, -1},
  { 7,  2,  3, -1,  6,  2,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 7,  0,  8, -1,  7,  6,  0, -1,  6,  2,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 2,  7,  6, -1,  2,  3,  7, -1,  0,  1,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  6,  2, -1,  1,  8,  6, -1,  1,  9,  8, -1,  8,  7,  6, -1, -1, -1, -1, -1},
  {10,  7,  6, -1, 10,  1,  7, -1,  1,  3,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {10,  7,  6, -1,  1,  7, 10, -1,  1,  8,  7, -1,  1,  0,  8, -1, -1, -1, -1, -1},
  { 0,  3,  7, -1,  0,  7, 10, -1,  0, 10,  9, -1,  6, 10,  7, -1, -1, -1, -1, -1},
  { 7,  6, 10, -1,  7, 10,  8, -1,  8, 10,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 6,  8,  4, -1, 11,  8,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 3,  6, 11, -1,  3,  0,  6, -1,  0,  4,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 8,  6, 11, -1,  8,  4,  6, -1,  9,  0,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 9,  4,  6, -1,  9,  6,  3, -1,  9,  3,  1, -1, 11,  3,  6, -1, -1, -1, -1, -1},
  { 6,  8,  4, -1,  6, 11,  8, -1,  2, 10,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  2, 10, -1,  3,  0, 11, -1,  0,  6, 11, -1,  0,  4,  6, -1, -1, -1, -1, -1},
  { 4, 11,  8, -1,  4,  6, 11, -1,  0,  2,  9, -1,  2, 10,  9, -1, -1, -1, -1, -1},
  {10,  9,  3, -1, 10,  3,  2, -1,  9,  4,  3, -1, 11,  3,  6, -1,  4,  6,  3, -1},
  { 8,  2,  3, -1,  8,  4,  2, -1,  4,  6,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  4,  2, -1,  4,  6,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  9,  0, -1,  2,  3,  4, -1,  2,  4,  6, -1,  4,  3,  8, -1, -1, -1, -1, -1},
  { 1,  9,  4, -1,  1,  4,  2, -1,  2,  4,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 8,  1,  3, -1,  8,  6,  1, -1,  8,  4,  6, -1,  6, 10,  1, -1, -1, -1, -1, -1},
  {10,  1,  0, -1, 10,  0,  6, -1,  6,  0,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 4,  6,  3, -1,  4,  3,  8, -1,  6, 10,  3, -1,  0,  3,  9, -1, 10,  9,  3, -1},
  {10,  9,  4, -1,  6, 10,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 4,  9,  5, -1,  7,  6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  8,  3, -1,  4,  9,  5, -1, 11,  7,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 5,  0,  1, -1,  5,  4,  0, -1,  7,  6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {11,  7,  6, -1,  8,  3,  4, -1,  3,  5,  4, -1,  3,  1,  5, -1, -1, -1, -1, -1},
  { 9,  5,  4, -1, 10,  1,  2, -1,  7,  6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 6, 11,  7, -1,  1,  2, 10, -1,  0,  8,  3, -1,  4,  9,  5, -1, -1, -1, -1, -1},
  { 7,  6, 11, -1,  5,  4, 10, -1,  4,  2, 10, -1,  4,  0,  2, -1, -1, -1, -1, -1},
  { 3,  4,  8, -1,  3,  5,  4, -1,  3,  2,  5, -1, 10,  5,  2, -1, 11,  7,  6, -1},
  { 7,  2,  3, -1,  7,  6,  2, -1,  5,  4,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 9,  5,  4, -1,  0,  8,  6, -1,  0,  6,  2, -1,  6,  8,  7, -1, -1, -1, -1, -1},
  { 3,  6,  2, -1,  3,  7,  6, -1,  1,  5,  0, -1,  5,  4,  0, -1, -1, -1, -1, -1},
  { 6,  2,  8, -1,  6,  8,  7, -1,  2,  1,  8, -1,  4,  8,  5, -1,  1,  5,  8, -1},
  { 9,  5,  4, -1, 10,  1,  6, -1,  1,  7,  6, -1,  1,  3,  7, -1, -1, -1, -1, -1},
  { 1,  6, 10, -1,  1,  7,  6, -1,  1,  0,  7, -1,  8,  7,  0, -1,  9,  5,  4, -1},
  { 4,  0, 10, -1,  4, 10,  5, -1,  0,  3, 10, -1,  6, 10,  7, -1,  3,  7, 10, -1},
  { 7,  6, 10, -1,  7, 10,  8, -1,  5,  4, 10, -1,  4,  8, 10, -1, -1, -1, -1, -1},
  { 6,  9,  5, -1,  6, 11,  9, -1, 11,  8,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 3,  6, 11, -1,  0,  6,  3, -1,  0,  5,  6, -1,  0,  9,  5, -1, -1, -1, -1, -1},
  { 0, 11,  8, -1,  0,  5, 11, -1,  0,  1,  5, -1,  5,  6, 11, -1, -1, -1, -1, -1},
  { 6, 11,  3, -1,  6,  3,  5, -1,  5,  3,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  2, 10, -1,  9,  5, 11, -1,  9, 11,  8, -1, 11,  5,  6, -1, -1, -1, -1, -1},
  { 0, 11,  3, -1,  0,  6, 11, -1,  0,  9,  6, -1,  5,  6,  9, -1,  1,  2, 10, -1},
  {11,  8,  5, -1, 11,  5,  6, -1,  8,  0,  5, -1, 10,  5,  2, -1,  0,  2,  5, -1},
  { 6, 11,  3, -1,  6,  3,  5, -1,  2, 10,  3, -1, 10,  5,  3, -1, -1, -1, -1, -1},
  { 5,  8,  9, -1,  5,  2,  8, -1,  5,  6,  2, -1,  3,  8,  2, -1, -1, -1, -1, -1},
  { 9,  5,  6, -1,  9,  6,  0, -1,  0,  6,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  5,  8, -1,  1,  8,  0, -1,  5,  6,  8, -1,  3,  8,  2, -1,  6,  2,  8, -1},
  { 1,  5,  6, -1,  2,  1,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  3,  6, -1,  1,  6, 10, -1,  3,  8,  6, -1,  5,  6,  9, -1,  8,  9,  6, -1},
  {10,  1,  0, -1, 10,  0,  6, -1,  9,  5,  0, -1,  5,  6,  0, -1, -1, -1, -1, -1},
  { 0,  3,  8, -1,  5,  6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {10,  5,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {11,  5, 10, -1,  7,  5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {11,  5, 10, -1, 11,  7,  5, -1,  8,  3,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 5, 11,  7, -1,  5, 10, 11, -1,  1,  9,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {10,  7,  5, -1, 10, 11,  7, -1,  9,  8,  1, -1,  8,  3,  1, -1, -1, -1, -1, -1},
  {11,  1,  2, -1, 11,  7,  1, -1,  7,  5,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  8,  3, -1,  1,  2,  7, -1,  1,  7,  5, -1,  7,  2, 11, -1, -1, -1, -1, -1},
  { 9,  7,  5, -1,  9,  2,  7, -1,  9,  0,  2, -1,  2, 11,  7, -1, -1, -1, -1, -1},
  { 7,  5,  2, -1,  7,  2, 11, -1,  5,  9,  2, -1,  3,  2,  8, -1,  9,  8,  2, -1},
  { 2,  5, 10, -1,  2,  3,  5, -1,  3,  7,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 8,  2,  0, -1,  8,  5,  2, -1,  8,  7,  5, -1, 10,  2,  5, -1, -1, -1, -1, -1},
  { 9,  0,  1, -1,  5, 10,  3, -1,  5,  3,  7, -1,  3, 10,  2, -1, -1, -1, -1, -1},
  { 9,  8,  2, -1,  9,  2,  1, -1,  8,  7,  2, -1, 10,  2,  5, -1,  7,  5,  2, -1},
  { 1,  3,  5, -1,  3,  7,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  8,  7, -1,  0,  7,  1, -1,  1,  7,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 9,  0,  3, -1,  9,  3,  5, -1,  5,  3,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 9,  8,  7, -1,  5,  9,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 5,  8,  4, -1,  5, 10,  8, -1, 10, 11,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 5,  0,  4, -1,  5, 11,  0, -1,  5, 10, 11, -1, 11,  3,  0, -1, -1, -1, -1, -1},
  { 0,  1,  9, -1,  8,  4, 10, -1,  8, 10, 11, -1, 10,  4,  5, -1, -1, -1, -1, -1},
  {10, 11,  4, -1, 10,  4,  5, -1, 11,  3,  4, -1,  9,  4,  1, -1,  3,  1,  4, -1},
  { 2,  5,  1, -1,  2,  8,  5, -1,  2, 11,  8, -1,  4,  5,  8, -1, -1, -1, -1, -1},
  { 0,  4, 11, -1,  0, 11,  3, -1,  4,  5, 11, -1,  2, 11,  1, -1,  5,  1, 11, -1},
  { 0,  2,  5, -1,  0,  5,  9, -1,  2, 11,  5, -1,  4,  5,  8, -1, 11,  8,  5, -1},
  { 9,  4,  5, -1,  2, 11,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 2,  5, 10, -1,  3,  5,  2, -1,  3,  4,  5, -1,  3,  8,  4, -1, -1, -1, -1, -1},
  { 5, 10,  2, -1,  5,  2,  4, -1,  4,  2,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 3, 10,  2, -1,  3,  5, 10, -1,  3,  8,  5, -1,  4,  5,  8, -1,  0,  1,  9, -1},
  { 5, 10,  2, -1,  5,  2,  4, -1,  1,  9,  2, -1,  9,  4,  2, -1, -1, -1, -1, -1},
  { 8,  4,  5, -1,  8,  5,  3, -1,  3,  5,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  4,  5, -1,  1,  0,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 8,  4,  5, -1,  8,  5,  3, -1,  9,  0,  5, -1,  0,  3,  5, -1, -1, -1, -1, -1},
  { 9,  4,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 4, 11,  7, -1,  4,  9, 11, -1,  9, 10, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  8,  3, -1,  4,  9,  7, -1,  9, 11,  7, -1,  9, 10, 11, -1, -1, -1, -1, -1},
  { 1, 10, 11, -1,  1, 11,  4, -1,  1,  4,  0, -1,  7,  4, 11, -1, -1, -1, -1, -1},
  { 3,  1,  4, -1,  3,  4,  8, -1,  1, 10,  4, -1,  7,  4, 11, -1, 10, 11,  4, -1},
  { 4, 11,  7, -1,  9, 11,  4, -1,  9,  2, 11, -1,  9,  1,  2, -1, -1, -1, -1, -1},
  { 9,  7,  4, -1,  9, 11,  7, -1,  9,  1, 11, -1,  2, 11,  1, -1,  0,  8,  3, -1},
  {11,  7,  4, -1, 11,  4,  2, -1,  2,  4,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {11,  7,  4, -1, 11,  4,  2, -1,  8,  3,  4, -1,  3,  2,  4, -1, -1, -1, -1, -1},
  { 2,  9, 10, -1,  2,  7,  9, -1,  2,  3,  7, -1,  7,  4,  9, -1, -1, -1, -1, -1},
  { 9, 10,  7, -1,  9,  7,  4, -1, 10,  2,  7, -1,  8,  7,  0, -1,  2,  0,  7, -1},
  { 3,  7, 10, -1,  3, 10,  2, -1,  7,  4, 10, -1,  1, 10,  0, -1,  4,  0, 10, -1},
  { 1, 10,  2, -1,  8,  7,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 4,  9,  1, -1,  4,  1,  7, -1,  7,  1,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 4,  9,  1, -1,  4,  1,  7, -1,  0,  8,  1, -1,  8,  7,  1, -1, -1, -1, -1, -1},
  { 4,  0,  3, -1,  7,  4,  3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 4,  8,  7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 9, 10,  8, -1, 10, 11,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 3,  0,  9, -1,  3,  9, 11, -1, 11,  9, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  1, 10, -1,  0, 10,  8, -1,  8, 10, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 3,  1, 10, -1, 11,  3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  2, 11, -1,  1, 11,  9, -1,  9, 11,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 3,  0,  9, -1,  3,  9, 11, -1,  1,  2,  9, -1,  2, 11,  9, -1, -1, -1, -1, -1},
  { 0,  2, 11, -1,  8,  0, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 3,  2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 2,  3,  8, -1,  2,  8, 10, -1, 10,  8,  9, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 9, 10,  2, -1,  0,  9,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 2,  3,  8, -1,  2,  8, 10, -1,  0,  1,  8, -1,  1, 10,  8, -1, -1, -1, -1, -1},
  { 1, 10,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 1,  3,  8, -1,  9,  1,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  9,  1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  { 0,  3,  8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1},
  {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
 };

 for (i=0; i<12; i++) v[i] = (ints[i])?(ints[i]->v):(NULL);
 for (i=0; i<20; i+=4)
 {
  if (mc_triTable[lu][i] != -1)
  {
   t[0] = mc_triTable[lu][i];
   t[1] = mc_triTable[lu][i+1];
   t[2] = mc_triTable[lu][i+2];
   if (v[t[0]] && v[t[1]] && v[t[2]])
   {
    e1 = tin->CreateEdge(v[t[0]], v[t[1]]);
    e2 = tin->CreateEdge(v[t[1]], v[t[2]]);
    e3 = tin->CreateEdge(v[t[2]], v[t[0]]);
	if (tin->CreateTriangle(e1, e2, e3)==NULL)
	{
		TMesh::warning("mc_grid::polygonize: triangle failed.\n");
	}
   }
   else
   {
	   TMesh::warning("mc_grid::polygonize: should not happen.\n");
	   for (int i = 0; i < 12; i++) printf("%c ", (ints[i] == NULL) ? ('N') : ((ints[i]->sg) ? ('I') : ('O')));
	   printf("\n");
   }
  }
 }
}


bool mc_grid::segmentIntersectsTriangle(Point& ev1, Point& ev2, Triangle *t, Point& op)
{
 coord d1, d2, o1, o2, o3;
 Vertex *v1 = t->v1(), *v2 = t->v2(), *v3 = t->v3();

 d1 = ev1.exactOrientation(v1,v2,v3);
 d2 = ev2.exactOrientation(v1,v2,v3);
 if ((d1==0 && d2==0) || (d1>0 && d2>0) || (d1<0 && d2<0)) return false;
 o1 = ev1.exactOrientation(&ev2, v1, v2);
 o2 = ev1.exactOrientation(&ev2, v2, v3);
 if ((o1>0 && o2<0) || (o1<0 && o2>0)) return false;
 o3 = ev1.exactOrientation(&ev2, v3, v1);
 if ((o1>0 && o3<0) || (o1<0 && o3>0)) return false;
 if ((o2>0 && o3<0) || (o2<0 && o3>0)) return false;

 //bool orat = coord::use_rationals;
 //coord::use_rationals = true;
 op = Point::linePlaneIntersection(ev1, ev2, v1, v2, v3);
// coord::use_rationals = orat;

 //d1 = FABS(d1); d2 = FABS(d2);
 //op = ((ev1*d2)+(ev2*d1))/(d1+d2);

 return true;
}

void mc_grid::sample_triangle(Triangle *t)
{
 Vertex *v1 = t->v1(), *v2 = t->v2(), *v3 = t->v3();
 coord minx = MIN(v1->x, MIN(v2->x, v3->x)); minx = ceil(minx);
 coord Mx = MAX(v1->x, MAX(v2->x, v3->x)); Mx = floor(Mx);
 coord miny = MIN(v1->y, MIN(v2->y, v3->y)); miny = ceil(miny);
 coord My = MAX(v1->y, MAX(v2->y, v3->y)); My = floor(My);
 coord minz = MIN(v1->z, MIN(v2->z, v3->z)); minz = ceil(minz);
 coord Mz = MAX(v1->z, MAX(v2->z, v3->z)); Mz = floor(Mz);
 int i, j;
 Point p;
 UBYTE sg;
 Point normal(t->getVector());

 p = (*v1)+Point(0,0,1); sg = (p.exactOrientation(v1, v2, v3) < 0)?(1):(0);
 for (i = TMESH_TO_INT(minx); i <= TMESH_TO_INT(Mx); i++)
  for (j = TMESH_TO_INT(miny); j <= TMESH_TO_INT(My); j++)
  {
	Point P1(i,j,minz-1), P2(i,j,Mz+1);
   if (segmentIntersectsTriangle(P1, P2, t, p))
   {xy[i+numrays*j-1-numrays].appendTail(newMcInts(p.z, sg, t)); }

  }

 p = (*v1)+Point(0,1,0); sg = (p.exactOrientation(v1, v2, v3) < 0)?(1):(0);
 for (i = TMESH_TO_INT(minx); i <= TMESH_TO_INT(Mx); i++)
  for (j = TMESH_TO_INT(minz); j <= TMESH_TO_INT(Mz); j++)
  {
	Point P1(i,miny-1,j), P2(i,My+1,j);
   if (segmentIntersectsTriangle(P1, P2, t, p))
   {xz[i+numrays*j-1-numrays].appendTail(newMcInts(p.y, sg, t)); }
  }

 p = (*v1)+Point(1,0,0); sg = (p.exactOrientation(v1, v2, v3) < 0)?(1):(0);
 for (i = TMESH_TO_INT(minz); i <= TMESH_TO_INT(Mz); i++)
  for (j = TMESH_TO_INT(miny); j <= TMESH_TO_INT(My); j++)
  {
	 Point P1(minx-1,j,i), P2(Mx+1,j,i);
   if (segmentIntersectsTriangle(P1, P2, t, p))
   {zy[i+numrays*j-1-numrays].appendTail(newMcInts(p.x, sg, t)); }
  }
}

void mc_grid::sort()
{
 int i,j;

 for (i=0; i<numrays; i++)
  for (j=0; j<numrays; j++)
  {
   xy[i+numrays*j].sort(mc_ints::compare);
   xz[i+numrays*j].sort(mc_ints::compare);
   zy[i+numrays*j].sort(mc_ints::compare);
  }
}


void mc_grid::purgeList(List *l)
{
 Node *n;
 mc_ints *mc1, *mc2;
 int numcells = numrays + 1;
 static BYTE *count = new BYTE[numcells];
 static int onumcells = numcells;

 if (numcells != onumcells)
 {
	 delete[] count;
	 count = new BYTE[numcells];
	 onumcells = numcells;
 }
 
 //int in = 0;
 //if (l->numels() < 2) return;
 //for (n = l->head(); n != NULL; n = n->next()) if (((mc_ints *)n->data)->sg == 1) in++; else in--;
 //if (in==0)
 //{
	// for (n = l->head(); n != NULL; n = n->next())
	// {
	//	 mc1 = (mc_ints *)n->data;
	//	 if (mc1->sg == 1) { if (in != 0) mc1->ic = -1; in++; } else if (mc1->sg == 0) { if (in != 1) mc1->ic = -1; in--; }
	// }
 //}
 //// Actual removal from list
 //for (n = l->head(); n->next() != NULL;)
 //if ((mc1 = (mc_ints *)n->data)->ic == -1) { n = n->next(); l->removeCell(n->prev()); delete mc1; } else n = n->next();
 //if (l->numels() && (mc1 = (mc_ints *)l->tail()->data)->ic == -1) { l->removeCell(l->tail()); delete mc1; }
 

 for (int i = 0; i < numcells; i++) count[i] = 0;

 // For each cell
 // Keep only first entering intersection and last existing one

 int ac, lc = -1;
 if (l->numels() < 2) return;
 for (n=l->head(); n != NULL; n=n->next())
 {
  mc1 = (mc_ints *)n->data;
  if (mc1->sg==1) // Only entering
  {
   if ((ac = TMESH_TO_INT(floor(mc1->ic))) == lc) mc1->ic = -1;
   else lc = ac;
   count[ac]++;
  }
 }
 lc = numcells+1;
 for (n=l->tail(); n != NULL; n=n->prev())
 {
  mc1 = (mc_ints *)n->data;
  if (mc1->sg==0) // Only exiting
  {
   if ((ac = TMESH_TO_INT(floor(mc1->ic))) == lc) mc1->ic = -1;
   else lc = ac;
   count[ac]--;
  }
 }

 // Actual removal from list
 for (n = l->head(); n->next() != NULL;)
  if ((mc1 = (mc_ints *)n->data)->ic == -1) { n = n->next(); l->removeCell(n->prev()); delete mc1; }
  else n = n->next();
 if (l->numels() && (mc1 = (mc_ints *)l->tail()->data)->ic == -1) { l->removeCell(l->tail()); delete mc1; }

 // Remove discordant intersections
 if (l->numels() < 2) return;
 for (n = l->head(); n->next() != NULL; n = n->next())
 {
  mc1 = (mc_ints *)n->data;
  mc2 = (mc_ints *)n->next()->data;
  int mc1c = TMESH_TO_INT(floor(mc1->ic));
  int mc2c = TMESH_TO_INT(floor(mc2->ic));
  if (mc1c == mc2c && mc1->sg != mc2->sg)
  {
	  if ((count[mc1c] >= 0 && mc1->sg == 1) || (count[mc1c] <= 0 && mc1->sg == 0)) mc2->ic = -1;
	  if ((count[mc2c] >= 0 && mc2->sg == 1) || (count[mc2c] <= 0 && mc2->sg == 0)) mc1->ic = -1;
  }
 }
 //for (n = l->head()->next(); n != l->tail(); n = n->next())
 //{
	// mc1 = (mc_ints *)n->data;
	// mc1->ic = -1;
 //}

 // Actual removal from list
 for (n = l->head(); n->next() != NULL;)
  if ((mc1 = (mc_ints *)n->data)->ic == -1) { n = n->next(); l->removeCell(n->prev()); delete mc1; }
  else n = n->next();
 if (l->numels() && (mc1 = (mc_ints *)l->tail()->data)->ic == -1) { l->removeCell(l->tail()); delete mc1; }
}

void mc_grid::purge()
{
 int i,j;

 for (i=0; i<numrays; i++)
  for (j=0; j<numrays; j++)
  {
   purgeList(&(xy[i+numrays*j]));
   purgeList(&(xz[i+numrays*j]));
   purgeList(&(zy[i+numrays*j]));
  }
}

void mc_grid::createVertices(List *l, int i, int j, int k)
{
 Node *n;
 mc_ints *mc;
 Vertex *v;
 coord trdc;

 i++; j++; k++;
 FOREACHNODE((*l), n)
 {
  mc = (mc_ints *)n->data;
  trdc = mc->ic;
  if (!k) v = tin->newVertex(i, j, trdc);
  else if (!j) v = tin->newVertex(i, trdc, k);
  else v = tin->newVertex(trdc, k, j);
  mc->v = new ExtVertex(v);
  tin->V.appendHead(v);
  v->info = mc->source;
 }
}

void mc_grid::createVertices()
{
 int i,j;

 for (i=0; i<numrays; i++)
  for (j=0; j<numrays; j++)
  {
   createVertices(&(xy[i+numrays*j]), i, j, -1);
   createVertices(&(xz[i+numrays*j]), i, -1, j);
   createVertices(&(zy[i+numrays*j]), -1, i, j);
  }
}

void mc_cell::merge(mc_cell *m)
{
	for (int i = 0; i<12; i++) if (m->ints[i] != NULL) ints[i] = m->ints[i];
	m->x = -1;
}

List *mc_grid::createCells()
{
 int i,j,k,numcells=numrays+1;
 mc_ints *m;
 Node *n;
 List *ac = new List;

 for (i=0; i<numrays; i++)
  for (j=0; j<numrays; j++)
  {
   FOREACHNODE(xy[i+numrays*j], n)
   {
    m = ((mc_ints *)n->data);
	k = TMESH_TO_INT(floor(m->ic));
    ac->appendTail(new mc_cell(i,j,k,m,5));
    ac->appendTail(new mc_cell(i,j+1,k,m,1));
    ac->appendTail(new mc_cell(i+1,j,k,m,7));
    ac->appendTail(new mc_cell(i+1,j+1,k,m,3));
   }
   FOREACHNODE(xz[i+numrays*j], n)
   {
    m = ((mc_ints *)n->data);
	k = TMESH_TO_INT(floor(m->ic));
	ac->appendTail(new mc_cell(i, k, j, m, 10));
    ac->appendTail(new mc_cell(i,k,j+1,m,9));
    ac->appendTail(new mc_cell(i+1,k,j,m,11));
    ac->appendTail(new mc_cell(i+1,k,j+1,m,8));
   }
   FOREACHNODE(zy[i+numrays*j], n)
   {
    m = ((mc_ints *)n->data);
	k = TMESH_TO_INT(floor(m->ic));
	ac->appendTail(new mc_cell(k, j, i, m, 6));
    ac->appendTail(new mc_cell(k,j+1,i,m,2));
    ac->appendTail(new mc_cell(k,j,i+1,m,4));
    ac->appendTail(new mc_cell(k,j+1,i+1,m,0));
   }
  }

 ac->sort(mc_cell::compare);
 mc_cell *mcc, *last = NULL;
 //int x,y,z;
 //x=y=z=-1;

 last = (mc_cell *)ac->head()->data;
 for (n = ac->head()->next(); n != NULL; n = n->next())
 {
  mcc = (mc_cell *)n->data;
  if (mcc->x == last->x && mcc->y == last->y && mcc->z == last->z) last->merge(mcc);
  else last = mcc;
 }

 //FOREACHNODE((*ac), n)
 //{
 // mcc = (mc_cell *)n->data;
 // if (mcc->x == x && mcc->y == y && mcc->z == z)
 // {
 //  if (last != NULL)
 //  {
 //   for (i=0; i<12; i++) if (mcc->ints[i] != NULL) last->ints[i] = mcc->ints[i];
 //  }
 //  x = mcc->x; mcc->x = -1;
 // }
 // else {x = mcc->x; last = mcc;}
 // y = mcc->y; z = mcc->z;
 //}

 n = ac->head();
 do
 {
	 mcc = (mc_cell *)n->data;
	 n = n->next();
	 if (mcc->x == -1) { ac->removeCell((n != NULL) ? (n->prev()) : ac->tail()); delete (mcc); }
 } while (n != NULL);

 return ac;
}

void mc_grid::trackOuterHull()
{
	int i, j, numcells = numrays + 1;
	mc_ints *m1, *m2;
	Edge *e0;
	Triangle *t0;
	List *ac;

	for (i = 0; i<numrays; i++)
	for (j = 0; j<numrays; j++)
	{
		ac = &xy[i + numrays*j];
		if (ac->numels()>1)
		{
			m1 = ((mc_ints *)ac->head()->data);
			m2 = ((mc_ints *)ac->tail()->data);
			e0 = m1->v->v->e0; t0 = (e0 && e0->t1) ? (e0->t1) : ((e0 && e0->t2) ? (e0->t2) : (NULL)); if (t0 && !IS_VISITED(t0)) tin->selectConnectedComponent(t0);
			e0 = m2->v->v->e0; t0 = (e0 && e0->t1) ? (e0->t1) : ((e0 && e0->t2) ? (e0->t2) : (NULL)); if (t0 && !IS_VISITED(t0)) tin->selectConnectedComponent(t0);
		}
		ac = &xz[i + numrays*j];
		if (ac->numels()>1)
		{
			m1 = ((mc_ints *)ac->head()->data);
			m2 = ((mc_ints *)ac->tail()->data);
			e0 = m1->v->v->e0; t0 = (e0 && e0->t1) ? (e0->t1) : ((e0 && e0->t2) ? (e0->t2) : (NULL)); if (t0 && !IS_VISITED(t0)) tin->selectConnectedComponent(t0);
			e0 = m2->v->v->e0; t0 = (e0 && e0->t1) ? (e0->t1) : ((e0 && e0->t2) ? (e0->t2) : (NULL)); if (t0 && !IS_VISITED(t0)) tin->selectConnectedComponent(t0);
		}
		ac = &zy[i + numrays*j];
		if (ac->numels()>1)
		{
			m1 = ((mc_ints *)ac->head()->data);
			m2 = ((mc_ints *)ac->tail()->data);
			e0 = m1->v->v->e0; t0 = (e0 && e0->t1) ? (e0->t1) : ((e0 && e0->t2) ? (e0->t2) : (NULL)); if (t0 && !IS_VISITED(t0)) tin->selectConnectedComponent(t0);
			e0 = m2->v->v->e0; t0 = (e0 && e0->t1) ? (e0->t1) : ((e0 && e0->t2) ? (e0->t2) : (NULL)); if (t0 && !IS_VISITED(t0)) tin->selectConnectedComponent(t0);
		}
	}
	tin->invertSelection();
	tin->removeSelectedTriangles();
}


mc_grid::mc_grid(Basic_TMesh *_tin, int n)
{
 numrays=n;
 xy=new List[n*n];
 xz=new List[n*n];
 zy=new List[n*n];
 tin = _tin;

 Point top;
 tin->getBoundingBox(origin, top);
 top-=origin;
 norm = MAX(top.x,MAX(top.y,top.z));
 norm /= (n+1);
 origin -= Point(norm/2, norm/2, norm/2);
 norm = MAX(top.x,MAX(top.y,top.z))/numrays;
}


void mc_grid::remesh(bool simplify_result)
{
 Vertex *v;
 Triangle *t;
 Node *n;
 Basic_TMesh ntin;
 ntin.V.joinTailList(&(tin->V));
 ntin.E.joinTailList(&(tin->E));
 ntin.T.joinTailList(&(tin->T));

 FOREACHVVVERTEX((&(ntin.V)), v, n) v->setValue(((*v)-origin)/norm); // Shift and normalize

 TMesh::begin_progress();
 int i=0;
 FOREACHVTTRIANGLE((&ntin.T), t, n)
 {
  sample_triangle(t); t->info=NULL;
  if (!((i++)%1000)) TMesh::report_progress("%d %% done   ",(i*50)/ntin.T.numels());
 }

 sort();		// Sort the intersections
 TMesh::report_progress("60 %% done   ");
 purge();		// Remove unused intersections
 TMesh::report_progress("70 %% done   ");
 createVertices(); 	// Create the new samples
 TMesh::report_progress("80 %% done   ");

 // Compute the list of active cells
 List *activeCells = createCells();
 TMesh::report_progress("90 %% done   ");
 mc_cell *c;
 while ((c=(mc_cell *)activeCells->popHead())!=NULL) c->polygonize(tin);
 TMesh::report_progress("95 %% done   ");


 tin->removeVertices();
 int count = tin->duplicateNonManifoldVertices();
 TMesh::info("Duplicated %d non-manifold vertices.\n",count);

 trackOuterHull();

 if (simplify_result)	FOREACHVVVERTEX((&ntin.V), v, n) v->setValue(((*v)*norm) + origin);	// Shift and normalize
 FOREACHVVVERTEX((&tin->V), v, n) v->setValue(((*v)*norm) + origin);	// Shift and normalize

 tin->safeCoordBackApproximation();

 if (simplify_result) simplify();
 TMesh::report_progress("99 %% done   ");

 FOREACHVVVERTEX((&tin->V), v, n){
 
  v->info = NULL;
 }
 FOREACHVTTRIANGLE((&ntin.T), t, n) if (t->info) { delete ((Point *)t->info); t->info = NULL; }
 TMesh::end_progress();
}











bool mc_safeCollapse(Edge *e)
{
	Point orig(e->v2);
	List *vt = e->v2->VT();
	Triangle *t;
	Node *n;
	Point nor;

	nor.setValue((Point *)e->v2->info);
	e->v2->setValue(e->v1);
	FOREACHVTTRIANGLE(vt, t, n) if (!t->hasEdge(e))
	{
		if (((*(t->v3())) + nor).exactOrientation(t->v1(), t->v2(), t->v3()) <= 0) break;
		if (t->nextVertex(e->v2)->info != e->v2->info) { if (((*(t->v3())) + (*(((Point *)t->nextVertex(e->v2)->info)))).exactOrientation(t->v1(), t->v2(), t->v3()) <= 0) break; }
		if (t->prevVertex(e->v2)->info != e->v2->info) { if (((*(t->v3())) + (*(((Point *)t->prevVertex(e->v2)->info)))).exactOrientation(t->v1(), t->v2(), t->v3()) <= 0) break; }
	}
	delete vt;
	e->v2->setValue(orig);
	orig.setValue(e->v1);
	return (n == NULL && e->collapse(orig));
}

//void mi_saveVRMLBorders(const char *filename, Basic_TMesh& tin)
//{
//	FILE *fp;
//	int i;
//	if ((fp = fopen(filename, "w")) == NULL) { TMesh::warning("Couldn't save graph!\n"); return; }
//
//	fprintf(fp, "#VRML V1.0 ascii\nSeparator {\nMaterial { diffuseColor 1 0 0 }\nCoordinate3 {\npoint [\n");
//	Node *n;
//	Edge *e;
//	Vertex *v;
//	i = 0;
//	FOREACHVVVERTEX((&tin.V), v, n)
//	{
//		v->printPoint(fp);
//		v->info = (void *)i;
//		i++;
//	}
//	fprintf(fp, "]\n}\n");
//
//	fprintf(fp, "Material { diffuseColor 0.7 0.7 1 }\n");
//	fprintf(fp, "IndexedLineSet {\ncoordIndex [\n");
//	FOREACHVEEDGE((&tin.E), e, n) if (!IS_SHARPEDGE(e))
//		fprintf(fp, "%ld, %ld, -1,\n", (j_voidint)e->v1->info, (j_voidint)e->v2->info);
//	fprintf(fp, "]\n}\n");
//
//	fprintf(fp, "Material { diffuseColor 1 0 0 }\n");
//	fprintf(fp, "IndexedLineSet {\ncoordIndex [\n");
//	FOREACHVEEDGE((&tin.E), e, n) if (IS_SHARPEDGE(e))
//		fprintf(fp, "%ld, %ld, -1,\n", (j_voidint)e->v1->info, (j_voidint)e->v2->info);
//	fprintf(fp, "]\n}\n");
//
//	fprintf(fp, "Material { diffuseColor 0 1 0 }\nDrawStyle { pointSize 4 }\n");
//
//	fprintf(fp, "Separator {\nCoordinate3 {\npoint [\n");
//	FOREACHVVVERTEX((&tin.V), v, n) if (IS_VISITED2(v))	v->printPoint(fp);
//	fprintf(fp, "]\n}\nPointSet {}\n}\n");
//
//	fprintf(fp, "}\n");
//	fclose(fp);
//}

//bool mi_getCenterPosition(Triangle *t, Vertex **cp)
//{
//	Vertex *v1 = t->v1(), *v2 = t->v2(), *v3 = t->v3();
//	Triangle *ot1 = (Triangle *)(((Point *)v1->info)->info);
//	Triangle *ot2 = (Triangle *)(((Point *)v2->info)->info);
//	Triangle *ot3 = (Triangle *)(((Point *)v3->info)->info);
//
//	Vertex *cv = ot1->v1();
//	if (!ot2->hasVertex(cv) || !ot3->hasVertex(cv)) cv = ot1->v2();
//	if (!ot2->hasVertex(cv) || !ot3->hasVertex(cv)) cv = ot1->v3();
//	if (!ot2->hasVertex(cv) || !ot3->hasVertex(cv)) return false;
//
//	*cp = cv;
//	return true;
//}

//Point mi_getCenterPosition(Edge *e)
//{
//	Vertex *v1 = e->v1, *v2 = e->v2;
//	Triangle *ot1 = (Triangle *)(((Point *)v1->info)->info);
//	Triangle *ot2 = (Triangle *)(((Point *)v2->info)->info);
//	if (ot1->commonEdge(ot2) == NULL) return e->getMidPoint();
//
//	Point nor1((Point *)v1->info), nor2((Point *)v2->info);
//	if (nor1*nor2 < 0 || nor1.getAngle(nor2)<0.01) return e->getMidPoint();
//
//	Point nor3 = e->toVector()&nor1;
//	Point d;
//	d.x = (nor1*(*v1));
//	d.y = (nor2*(*v2));
//	d.z = (nor3*(*v2));
//	return d.linearSystem(nor1, nor2, nor3);
//}

void mc_grid::simplify()
{
	Vertex *v;
	Triangle *t;
	Edge *e;
	Node *n;
	Point *nnor;


	// This turns info-pointed triangles to info-pointed normals.
	// In their turn, normals info-point their triangles.
	FOREACHVVVERTEX((&tin->V), v, n)
	{
			t = ((Triangle *)v->info);
			if (t->info != NULL) nnor = (Point *)t->info;
			else t->info = nnor = new Point(t->getVector());
			v->info = nnor;
			nnor->info = t;
	}

	FOREACHVEEDGE((&tin->E), e, n) if (e->isOnBoundary() || e->v1->info != e->v2->info) { MARK_VISIT(e); MARK_VISIT(e->v1); MARK_VISIT(e->v2); }
	FOREACHVTTRIANGLE((&tin->T), t, n) if (IS_VISITED(t->e1) && IS_VISITED(t->e2) && IS_VISITED(t->e3))
		{ MARK_VISIT2(t->v1()); MARK_VISIT2(t->v2()); MARK_VISIT2(t->v3()); }

	List ies;
	FOREACHVEEDGE((&tin->E), e, n)
	 if (!e->isOnBoundary() && e->v1->info == e->v2->info) ies.appendTail(e);
	 else if (e->isOnBoundary()) { MARK_VISIT2(e->v1); MARK_VISIT2(e->v2); }
	Point nor;
	int c;
	do
	{
		c = 0;
		FOREACHVEEDGE((&ies), e, n) if (e->isLinked() && !e->isOnBoundary() && e->v1->info == e->v2->info)
		{
		 if (IS_VISITED2(e->v1) && IS_VISITED2(e->v2)) continue;
		 if (IS_VISITED(e->v1) && IS_VISITED(e->v2) && e->t1->oppositeVertex(e)->info == e->v1->info && e->t2->oppositeVertex(e)->info == e->v1->info) continue;

		 if (IS_VISITED2(e->v2)) e->invert();
		 else if (IS_VISITED(e->v2) && !IS_VISITED2(e->v1)) e->invert();
		 if (mc_safeCollapse(e)) c++;
		} 

		//FOREACHVEEDGE((&ies), e, n) if (e->isLinked() && !(IS_VISITED(e->v1) && IS_VISITED(e->v2)))
		//{
		//	double a = e->delaunayMinAngle();
		//	nor.setValue((Point *)e->v2->info);
		//	if (e->swap()) { if ((e->t1->getVector()*nor<0) || (e->t2->getVector()*nor<0) || e->delaunayMinAngle() <= a) e->swap(true); }
		//}
	} while (c);

	tin->removeUnlinkedElements();
	tin->deselectTriangles();
	FOREACHVEEDGE((&tin->E), e, n) e->mask = 0;
	FOREACHVVVERTEX((&tin->V), v, n) v->mask = 0;
}

} //namespace T_MESH
